package cn.lena.lilisi;

/**
 * @author lena
 * @date 2021/8/11
 */
public class Main {

	public static void main(String[] args) {
		ListNode head=new ListNode(1);
		ListNode l=head;
		for(int i=2;i<10;i++) {
			l.next=new ListNode(i);
			l=l.next;
		}
/*		ListNode head=new ListNode(2);
		head.next=new ListNode(1);
		head.next.next=new ListNode(2);
		head.next.next.next=new ListNode(1);*/

/*		ListNode head=new ListNode(1);
		head.next=new ListNode(2);*/
		ListNode listNode = formatList2(head);

		while(listNode != null) {
			System.out.println("return:"+listNode.val);
			listNode=listNode.next;
		}

/*		int[] arr={1,2,1};
		int k=2;
		System.out.println(ans(arr,k));*/
	}

	/**
	 * 将a数组看成一个环形,分成两部分后最小差值是多少
	 * @param a
	 * @return
	 */
	public long minimum (int[] a) {
		if(a.length == 2) {
			return Math.abs(a[0]-a[1]);
		}
		int i=1;
		int si=0;
		int j=a.length-1;
		int sj=0;
		while(i != j) {
			if(si+a[i] <= sj+a[j]) {

			}
		}
		return 0;
	}

	/**
	 * 60% 暴力
	 * 二元组个数：找到array[i]+array[j]<=k有几个 i<j
	 * @param array [3,1,2]
	 * @param k 5
	 * @return 3
	 */
	public static long ans2 (int[] array, int k) {
		// 不能存储当前次数，之后遇到相同的相加，因为后面的个数不一定一样
		//Map<Integer,Long> map=new HashMap<>();
		long res=0;
		for(int i=0;i<array.length-1;i++) {
/*			if(map.get(array[i]) != null) {
				// 该值已经查询过
				res += map.get(array[i]);
				// 进入下一次循环
				continue;
			}*/
			long cur=0;
			for(int j=i+1;j<array.length;j++) {
				if(array[i]+array[j] <= k) {
					cur++;
				}
			}
			//map.put(array[i],cur);
			res += cur;
		}
		return res;
	}

	/**
	 * ac60%
	 * @param array
	 * @param k
	 * @return
	 */
	public long ans (int[] array, int k) {
		long res=0;
		for(int i=0;i<array.length-1;i++) {
			for(int j=i+1;j<array.length;j++) {
				if(array[i]+array[j] <= k) {
					res++;
				}
			}
		}
		return res;
	}

	public static ListNode formatList (ListNode head) {
		// 重新开辟一个链表空间
		ListNode pH=new ListNode(0);
		ListNode p=head;
		pH.next=p;
		ListNode pT=pH.next;
		while(p != null) {
			// 尾部
			pT.next=new ListNode(p.val);
			pT=pT.next;
			p=p.next;
			// 头部
			if(p == null) {
				break;
			}
			ListNode p2=pH.next;
			ListNode p3=p.next;
			pH.next=p;
			p.next=p2;
			p=p3;
		}
		return pH.next;
	}

	/**
	 * 100%
	 * 格式化链表：从头结点开始，依次插入尾结点、头结点
	 * @param head {1,2,3,4,5}
	 * @return {5,3,1,2,4}
	 */
	public static ListNode formatList2 (ListNode head) {
		if(head == null || head.next == null) {
			return head;
		}
		// 虚构一个头节点
		ListNode ph=new ListNode(0);
		ph.next=head;
		ListNode pt=ph.next;
		ListNode p=pt.next;
		while(p != null) {
			// p为当前要插入节点
			// 插入尾节点
			pt.next=p;
			pt=pt.next;
			// 插入头节点
			p=p.next;
			if(p == null) {
				break;
			}
			ListNode p3=p.next;
			ListNode p2=ph.next;
			ph.next=p;
			p.next=p2;
			p=p3;
		}
		pt.next=null;
		return ph.next;
	}

}
class ListNode {
   int val;
   ListNode next = null;
   public ListNode(int val) {
     this.val = val;
   }
}
